package com.algorithm.learning.sort;


import java.util.Arrays;

/**
 * @program: algorithm-learning
 * @description: 根据步长来进行排序合并
 * @author: YuKai Fan
 * @create: 2024/8/18 20:25
 **/
public class 归并排序_非递归 {

    public static void main(String[] args) {
        int[] nums = { 6, 7, 8, 9, 10, 1, 2, 3, 4, 5};
        new 归并排序_非递归().mergeSort2(nums);
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 这里
     * @param arr
     */
    public void mergeSort2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int step = 1;
        int n = arr.length;
        // 只有步长小于总长度的时候，才能继续
        // 当步长等于或超过总长度，此时右数组已经没有了，就没必要排序了
        while (step < n) {
            int l = 0;
            // 左数组需要小于n，否则随着step的增大，l可能会大于n，导致越界
            while (l < n) {
                int m = 0;
                // 这里判断表示，如果总长度减去左数组长度大于step，表示没有越界，直接l+step-1即可
                // 否则l+step-1必定越界，此时，左数组的长度就是n-l
                if (n - l >= step) {
                    m = l + step - 1;
                } else {
                    m = n - 1;
                }
                // L ... M
                if (m == n - 1) {
                    break;
                }
                // L .. M, M + 1 ... R
                int r = 0;
                if (n - 1 - m >= step) {
                    r = m + 1 + step -1;
                } else {
                    r = n - 1;
                }
                merge(arr, l, m, r);
                if ( r == n - 1) {
                    break;
                } else {
                    l = r + 1;
                }
            }

            // 要注意，如果数组长度很长，逼近2^32-1的话，那么step就会溢出
            // 所以这里不能用 step *= 2;
            if (step > n / 2) {
                break;
            } else {
                step *= 2;
            }
        }
    }

    private void merge(int[] arr, int l, int m, int r) {
        int[] temp = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = m + 1;
        while (p1 <= m && p2 <= r) {
            temp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= m) {
            temp[i++] = arr[p1++];
        }
        while (p2 <= r) {
            temp[i++] = arr[p2++];
        }
        for (int j = 0; j < temp.length; j++) {
            arr[l + j] = temp[j];
        }
    }
}
